package LearnAlgorithm.j_动态规划and贪心算法;

import java.util.Scanner;

/*
求最大公共子序列问题
可以隔位选取子序列，但是必须顺序从左到右
in
AB34C
A1BC2

out
ABC

*/
public class i最长公共子序列LCSbyDP {
	public static void main(String[] args) {
		i最长公共子序列LCSbyDP test = new i最长公共子序列LCSbyDP();
		test.useDP();
	}
	
	/**
	 * 前置方法
	 */
	public void useDP() {
		Scanner scanner = new Scanner(System.in);
		String s1 = scanner.next();
		String s2 = scanner.next();
		int len1 = s1.length();
		int len2 = s2.length();
		int[][] dp = new int[len1 + 1][len2 + 1];//没有使用索引=0的row与col;所以才+1
		String res = DP(s1, s2, dp, len1, len2);
		System.out.println(res);
	}
	
	/**
	 * 动态规划
	 * @param s1
	 * @param s2
	 * @param dp
	 * @param len1
	 * @param len2
	 * @return
	 */
	public String DP(String s1, String s2, int[][] dp, int len1, int len2) {
		int flag = 0;//定义最新状态；这个状态是：长度i的字符串生产的；用于长度i+1的串，在比较时提供参考用的
		for (int i = 1; i <= len1; i++) {//初始化第一列；i代表元素个数；O(len1)
			if (flag == 1) {
				dp[i][1] = 1;//记录一个“相等”
			} else if (s1.charAt(i - 1) == s2.charAt(0)) {//s1的第i个元素 == s2的首元素
				dp[i][1] = 1;//记录一个“相等”
				flag = 1;//更改“最新状态”
			} else {
				dp[i][1] = 0;//记录一个“不等”
			}
		}
		flag = 0;//重置“最新状态”
		for (int i = 1; i <= len2; i++) {//初始化第一行；i代表元素个数；O(len2)
			if (flag == 1) {
				dp[1][i] = 1;//记录一个“相等”
			} else if (s2.charAt(i - 1) == s1.charAt(0)) {
				dp[1][i] = 1;//记录一个“相等”
				flag = 1;//更改“最新状态”
			} else {
				dp[1][i] = 0;//记录一个“不等”
			}
		}
		for (int row = 2; row <= len1; row++) {//O(len1*len2)；开始真正生成dp表
			for (int col = 2; col <= len2; col++) {
				int maxFromLeftOrUP = Math.max(dp[row - 1][col], dp[row][col - 1]);//选择出上与左中最大的值A；我们设左上的值为B
				if (s1.charAt(row - 1) == s2.charAt(col - 1)) {//判断两串当前索引的字符相等
					dp[row][col] = dp[row - 1][col - 1] + 1;//真相等！dp当前的位置那么等于B+1
				} else {//不等
					dp[row][col] = maxFromLeftOrUP;//把A继承给dp当前的位置
				}
			}
		}
		return fromDPGenerateString(dp, s1, s2, len1, len2);
	}
	
	/**
	 * 根据dp数组生成字符串
	 * @param dp
	 * @param s1
	 * @param s2
	 * @param row
	 * @param col
	 * @return
	 */
	public String fromDPGenerateString(int[][] dp, String s1, String s2, int row, int col) {
		StringBuilder helper = new StringBuilder();
		while (row > 0 && col > 0) {
			if (dp[row][col] > Math.max(dp[row - 1][col], dp[row][col - 1])) {//当前位置比左和上都要大；那么当前位置一定是被+1的位置；此位置有两串相同的字符；这里有个巧妙的地方，第1我们没用到0行0列，第2我们运用Math.max(dp[row - 1][col], dp[row][col - 1])方法，即便其中一个参数因为涉及到了0行0列，max()也会给出正确的结果(即返回逻辑上正确的参数A，因为A > 0)，所以依靠max()我们做到了“考虑了dp边界的情况”
				helper.insert(0, s1.charAt(row - 1));//插入该字符A到开头；s1.charAt(row)是选中A；其实完全也可以写s2.charAt(col)
				//下面两句是为了“斜向左上走”
				row--;
				col--;
			} else {//左和上之间有一个最大
				if (dp[row - 1][col] > dp[row][col - 1]) {//选出最大的那个
					row--;//上大，行-1，也就是把当前位置向上移1
				} else {
					col--;//左大，列-1，也就是把当前位置向左移1
				}
			}
		}
		return helper.toString();
	}
}
